Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Sort Colors

Problem Statement

Given an array containing 0s, 1s and 2s, sort the array in-place. You should treat numbers of the array as objects, hence, we can’t count 0s, 1s, and 2s to recreate the array.

The flag of the Netherlands consists of three colors: red, white and blue; and since our input array also consists of three different numbers that is why it is called Dutch National Flag problem.

Examples

Example 1

  • Input: arr = [1, 0, 2, 1, 0]
  • Output: [0, 0, 1, 1, 2]
  • Explanation:
    • All 0s are moved to the front, 1s in the middle, and 2s at the end.
    • The relative order within each group doesn't matter.

Example 2

  • Input: arr= [2, 2, 0, 1, 2, 0]
  • Output: [0, 0, 1, 2, 2, 2]
  • Explanation:
    • All 0s come first, followed by the 1, and then all 2s at the end.
    • Sorting is done in-place without using extra space or counting.

Constraints:

  • n == arr.length
  • 1 <= n <= 300
  • arr[i] is either 0, 1, or 2.

Solution

The brute force solution will be to use an in-place sorting algorithm like Heapsort which will take . Can we do better than this? Is it possible to sort the array in one iteration?

We can use a Two Pointers approach while iterating through the array. Let’s say the two pointers are called low and high which are pointing to the first and the last element of the array respectively. So while iterating, we will move all 0s before low and all 2s after high so that in the end, all 1s will be between low and high. In the end, all 0s are on the left, all 1s are in the middle, and all 2s are on the right.

Step-by-Step Algorithm

  1. We start by initializing three variables: low to 0, high to the last index of the array, and i also to 0. Low is meant to keep track of the latest position where a 0 should be placed, high is meant to keep track of the latest position where a 2 should be placed, and i is used to iterate through the array.

  2. We then start a loop that continues as long as i is less than or equal to high. In each iteration of the loop, we check the value of the array at the index i.

  3. If the value is 0, we swap the values at the indices i and low. We then increment both i and low, since we know that the new element at low is 0 (sorted in its correct place) and we can move to the next index.

  4. If the value is 1, we do nothing other than increment i. This is because we want 1s to be in the middle of the array.

  5. If the value is 2, we swap the values at i and high. However, after the swap, we only decrement high without incrementing i. This is because the new value at index i (after the swap) could be 0, 1 or 2, and we need to check this value again in the next iteration.

  6. The swap function simply switches the values at two given indices in the array.

  7. The process continues until i is greater than high, at which point every element in the array has been checked and placed in its correct position. Hence, the array is now sorted.

Algorithm Walkthrough

Image

Initial State:

  • Array: [1, 0, 2, 1, 0]
  • low = 0, high = 4
  • i = 0

Step-by-Step Walkthrough:

  1. First Iteration (i = 0):

    • arr[i] = 1
    • Since it's 1, just increment i.
    • State after iteration:
      • Array: [1, 0, 2, 1, 0]
      • low = 0, high = 4
      • i = 1
  2. Second Iteration (i = 1):

    • arr[i] = 0
    • Swap arr[i] with arr[low] (Swap positions 1 and 0).
    • Increment low and i.
    • State after iteration:
      • Array: [0, 1, 2, 1, 0]
      • low = 1, high = 4
      • i = 2
  3. Third Iteration (i = 2):

    • arr[i] = 2
    • Swap arr[i] with arr[high] (Swap positions 2 and 4).
    • Decrement high.
    • i remains the same to check the swapped element.
    • State after iteration:
      • Array: [0, 1, 0, 1, 2]
      • low = 1, high = 3
      • i = 2
  4. Fourth Iteration (i = 2):

    • arr[i] = 0
    • Swap arr[i] with arr[low] (Swap positions 2 and 1).
    • Increment low and i.
    • State after iteration:
      • Array: [0, 0, 1, 1, 2]
      • low = 2, high = 3
      • i = 3
  5. Fifth Iteration (i = 3):

    • arr[i] = 1
    • Since it's 1, just increment i.
    • State after iteration:
      • Array: [0, 0, 1, 1, 2]
      • low = 2, high = 3
      • i = 4

Final State:

  • Array: [0, 0, 1, 1, 2]
  • All 0s are at the beginning, followed by all 1s, and all 2s at the end.

Code

Here is what our algorithm will look like:

Java

. . . .

Complexity Analysis

Time Complexity

  • Single pass through the array: The algorithm uses a single for loop that iterates through the array once. The pointer i moves from the start to the end of the array, and at each iteration, it processes the current element.
  • Swaps: Each swap operation occurs in constant time . Since each element is either swapped or incremented only once, the number of swaps and comparisons is proportional to the length of the array.

Overall time complexity: Since the algorithm processes each element of the array exactly once, the time complexity is , where N is the number of elements in the array.

Space Complexity

  • In-place modification: The algorithm sorts the array in place, meaning that it doesn't require any additional space that scales with the size of the input array.
  • Auxiliary space: The only extra space used is for a few integer variables (low, high, and i), which require constant space, .

Overall space complexity: Since the algorithm does not use any additional data structures, the space complexity is .

Sort Colors (medium)
Group Anagrams (Medium)
Mark as Completed

On this page

Problem Statement

Examples

Example 2

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity